class Solution
{
public:
    int firstBadVersion(int n)
    {
        long min = 0;
        long max = n - 1;
        while (min < max)
        {
            int mid = (min + max) / 2;
            if (isBadVersion(mid + 1))
            {
                max = mid;
            }
            else
            {
                min = mid + 1;
            }
        }
        return min + 1;
    }
};